package com.jerry.basic.mergesort;
import com.jerry.basic.sortutil.*;
public class MergeSort {
	/**
	 * @param args
	 * @author Jerry
	 */   
	public static void main(String[] args){
		int [] arrays = {8,3,5,1,7,9,4,0,2};
	    SortUtil.printArrays(Merge_Sort(arrays,0,8));
	}
	public static void Merge(int[] arr,int p,int q,int r){
		int len1 = q-p+1;
		int len2 = r-q;
		int[] left = new int[len1+1];
		int[] right = new int[len2+1];
		for(int i = 0;i<len1;i++)
			left[i]=arr[p+i];
		left[len1] = 999999;
		for(int j = 0;j<len2;j++)
			right[j]=arr[q+1+j];
		right[len2] = 999999;
		int lt = 0;
		int rt = 0;
		int k = p;
	    while(k<=r){
	    	if(left[lt]<=right[rt]){
	    		arr[k]=left[lt];
	    		lt++;
	    		k++;
	    	}
	    	else{
	    		arr[k]=right[rt];
	    		rt++;
	    		k++;
	    	}
	    }
		
	}
	
	public static int[] Merge_Sort(int[] arr,int p ,int r){
		int len = arr.length;
		if(0 == len)
			return null;
		else{
			if(p<r){
				int q = (p+r)/2;
				Merge_Sort(arr,p,q);
				Merge_Sort(arr,q+1,r);
				Merge(arr,p,q,r);
			}
			return arr;
		}
	}
}
